home *** CD-ROM | disk | FTP | other *** search
/ Shareware Grab Bag / Shareware Grab Bag.iso / 007 / sortc.arc / SORTC.C < prev   
Encoding:
C/C++ Source or Header  |  1987-07-13  |  39.0 KB  |  1,325 lines
  1. /*
  2.  *                s o r t c . c
  3.  *
  4.  * Sort utility
  5.  */
  6.  
  7. #ifdef    DOCUMENTATION
  8.  
  9. title    sort    Sort Data Files
  10. index        Sort Data Files
  11.  
  12. synopsis
  13.  
  14.     sortc [-options] [-oOUTFILE] [file ...]
  15.  
  16. description
  17.  
  18.     Sortc sorts all of the named files together and writes the result
  19.     to the standard output or to the file named in the -o option.
  20.     The standard input is sorted if no file names are supplied; sort
  21.     may thus be used as a filter.
  22.     .s
  23.     The output file may be the same as one of the input files.
  24.     .s
  25.     The default sort is ascending in ASCII collating sequence
  26.     using the entire line.  Upper and lower case are considered
  27.     different.  Using optional arguments, up to ten key fields
  28.     may be specified.  Lines with equal keys are further ordered
  29.     using the entire line as a single ASCII key.
  30.     .s
  31.     The following options apply to the entire sort:
  32.     .s.lm +4
  33.     .s.i-4;-o##The sorted output is written to the named file
  34.     instead of to the standard output.  The file may be the
  35.     same as one of the input files.
  36.     .s.i-4;-u##(Unique) only the first of a set of lines
  37.     having equal keys is output.  Only the specified keys are
  38.     considered in the definition of 'unique.'
  39.     .s.i-4;-v##(Verbose) Print elapsed time, etc.
  40.     .s.lm -4
  41.     The following options define the form of the sort.  If they
  42.     preceed the first key field definition, they define the default
  43.     for all keys.  If the option includes a key definition, only
  44.     that key is affected.
  45.     .s.lm +4
  46.     .s.i-4;-b##(Blank) causes leading whitespace in the key
  47.     field to be ignored.
  48.     .s.i-4;-d##(Dictionary) sorts in dictionary order;  only
  49.     letters, digits, and blanks are considered in the compare,
  50.     all else is ignored.  (Note: national letters (with values greater
  51.     than 128 decimal) are not processed correctly.)
  52.     .s.i-4;-f##(Fold case) folds all letters to lower-case for
  53.     comparisons.
  54.     .s.i-4;-i##(Ignore whitespace) causes all non-printing characters
  55.     to be ignored.
  56.     .s.i-4;-k##(Key) selects a field to be used as a sort key.
  57.     Up to ten key fields can be specified.  The keys are in order
  58.     of decreasing significance.  Key fields are compared, beginning
  59.     with the most significant one, until a not-equal key is found.
  60.     .s
  61.     The format of the -k option is "-kM1.N1,M2.N2"  The formatting
  62.     flags "bdfinrt?" may be applied to a particular key by preceeding
  63.     the 'k' appropriately as will be shown in the examples.
  64.     .s
  65.     The values following the "-k" define the starting and ending
  66.     position of the key using a field/offset value:
  67.     .lm+8
  68.     .s.i-8;M1.N1##Start of the key position (first character that
  69.     is to be compared).
  70.     .s.i-8;M2.N2##End of the key position (first character after
  71.     the key).
  72.     .lm-8
  73.     The 'M' values define the number of fields to skip, from the
  74.     start of the data line.  (0 means "skip no fields").
  75.     .s
  76.     The 'N' values define the number of bytes to skip in the
  77.     selected field.
  78.     .s
  79.     If "M1.N1" are omitted, start at the beginning of the line.
  80.     If "M2.N2" are omitted, end at the end of the line.
  81.     Except for "M2.N2" being omitted, omitting any of the four
  82.     values means "use zero" for that value.
  83.     .s
  84.     Neither of these specifiers will go beyond the end of the line.
  85.     A record can have a null key if the start-of-key is on or
  86.     after the end-of-key or at or after the end-of-line.
  87.     A null key is lower than any non-null key.
  88.     .s
  89.     If -b was specified, leading whitespace is skipped after
  90.     advancing to the M1 (M2) field, but before advancing by
  91.     N1 (N2) characters.
  92.     .s.i-4;-n##(Numeric) changes the sort ordering to ascending
  93.     arithmetic on a leading signed integer numeric string.
  94.     .s.i-4;-r##(Reverse) changes the sort ordering from ascending
  95.     to descending.
  96.     .s.i-4;-t?#(Terminator) changes the field terminator.  The
  97.     new definition is:
  98.     .s.lm+4
  99.     String of zero or more characters ending with the '?' character.
  100.     .s.lm-4
  101.     The terminator character may be escaped by using the backslash
  102.     convention.  By default, whitespace (blanks or tabs) terminates
  103.     a field.
  104.     .lm-4
  105.  
  106. Examples of Key Field Selection
  107.  
  108.     .br;Let a record be "ABC#DEF##########GHI"
  109.     .s.nf
  110.     Flag        Key field
  111.     -k1        " DEF         GHI"
  112.     -bk1        "DEF         GHI"
  113.     -bk1.1        "EF         GHI"
  114.     -bk1,2        "DEF         "
  115.     -k1,1        "" (Null field)
  116.     -k1.0,2.1    " DEF "
  117.     -bk1.0,2.1    "DEF         G"
  118.     -k0.1,1.3    "BC DE"
  119.     -k1.0,2.0    " DEF"
  120.     -k0.5,1.0    "" (Null field)
  121.     .s.f
  122.     Let a record be "ABC,DEFGHIJ,KLM"
  123.     .s.nf
  124.     Flag        Key field
  125.     -t,k1        "DEFGHIJ,KLM"
  126.     -t,k1,2        "DEFGHIJ,"
  127.     -t,k0.1,0.6    "BC,DE"
  128.     -t,k1.0,0.10    "DEFGHI"
  129.     .f    
  130.  
  131. Files
  132.  
  133.     sort.tmp
  134.  
  135. diagnostics
  136.  
  137.     The following messages occur on a non-severe error. SORTC
  138.     will exit with "error" status.
  139.  
  140.     .lm +8
  141.     .s.i -8;"?SORT-F-Cannot create temp. file"
  142.     .br
  143.     The required temporary file cannot be created  in  the
  144.     current directory.
  145.     .s.i -8;"?SORT-F-Cannot open input file."
  146.     .br
  147.     An input file cannot be accessed for reading.
  148.     .s.i -8;"?SORT-F-Cannot create output file."
  149.     .br
  150.     An output file cannot be  created  for writing.
  151.     .s.i -8;"?SORT-F-Out of space."
  152.     .br
  153.     There was insufficient memory space for the sort.
  154.     .lm -8
  155.     The following messages occur on a severe error. SORT will
  156.     exit with "severe error" status. Get help.
  157.     .s
  158.     .nf
  159.     "?SORT-U-Unexpected end of file"
  160.     "?SORT-U-Empty run"
  161.     "?SORT-U-temp. file"
  162.     .f
  163. author
  164.  
  165.     David Conroy
  166.     .s
  167.     Very slightly modified by Martin Minow
  168.     .s.nf
  169.     Extensively modified by
  170.       Ray Van Tassle
  171.       Motorola
  172.       1301 E. Algonquin Rd.
  173.       Room 4135
  174.       Shaumburg, Ill.
  175.       (312)-576-6017
  176.  
  177. Bugs
  178.  
  179. Internal
  180.  
  181.     See the source of sortc.c for a discussion of Workfile strategies
  182.     and sort timings.
  183.  
  184. #endif
  185.  
  186. /*
  187.  *
  188.  *   
  189.  * Work-file(s)
  190.  *   This program uses a Quicksort for the distribution phase (creating
  191.  *   runs of sorted lines) and puts each run into a work file. In essence,
  192.  *   the merge is one n-way merge onto the output file. ("n" is the number
  193.  *   of runs created in the 1st pass, as the file position is saved for each
  194.  *   run).
  195.  *   
  196.  * During the distribution (input) phase, the sorted array (line)
  197.  * is used as a heap while putting the run out to the work file.
  198.  * We replace the lines with input lines, to attempt to increase the size
  199.  * of the run. It is muchly and widely claimed that this doubles the
  200.  * average run size.
  201.  * My experiments bear this out. This should make the merge phase
  202.  * go faster (less runs).
  203.  * Oh hell. It turns out that doing so greatly increases the time
  204.  * of the distribution phase (50% to 100%) but decreases the time of the
  205.  * merge phase only a little bit. Perhaps it would help
  206.  * in a very specialized environment, where you could make several
  207.  * merge work-files, all on different devices, and have them contiguous,
  208.  * so that you wouldn't have the overhead of arm seeks.
  209.  * The absolute best you could ever hope to do would require 2 passes
  210.  * over the data: one for the distribution phase, and one for
  211.  * the merge phase. According to one of my books, about the best
  212.  * thing to use with several work files is a "three file polyphase merge",
  213.  * with a Fibonacci series for the number of runs on each file.
  214.  * The quoted figures are 2.7-4.6 equivalent passes over the entire data
  215.  * (polyphase is rough to figure exactly, because it does not pass the
  216.  * entire file on each pass).
  217.  * My figures on several varied files are the entire sort taking anywhere
  218.  * from 3 to 5 times as long as just passing the file thru a pgm which
  219.  * converts it to lower case. This seems quite good, as the time spent
  220.  * in doing comparisons is hefty. Maybe changine the way we do the
  221.  * merge could improve things a lot, but I don't think so. Anyway, this
  222.  * is a pretty neat trick, cramming all the runs into one file.
  223.  *
  224.  *
  225.  * I also pre-read several lines from each run whenever I do a seek
  226.  * to that run (this is H_P_READ). This improves the time of the merge
  227.  * phase by making it as much as ten (!!!) times faster. Evidently,
  228.  * the seek time is the dominating factor of this phase, and
  229.  * reading in several lines at each seek buys us a whole lot. Note that
  230.  * each actual read operation gets 512 bytes, which is usually several
  231.  * lines, so we have done all the work to get many lines, so
  232.  * we might as well take advantage of that fact and save some of them.
  233.  * It turns out that there is very little to be gained by increasing the
  234.  * size of the pre-read from 5 to 10 lines. I suspect that most
  235.  * of the improvement is in going from none to 1, and each incremental line
  236.  * that is added gains less than the last.
  237.  *
  238.  * Doing all these things, and increasing the size of the in-core sort
  239.  * area (MX_RLINE) will make this a pretty fast sort program.
  240.  *
  241.  * Some timings:
  242.  *  which   distr   merge   runs (distr,merge times in seconds 11/70)
  243.  *   Orig   327.2   146.1   214   Joe Sventeks DICT 45000 words
  244.  *   This   171     177      75   same (The file is already sorted)
  245.  *   pass   117                   convert it to lower case (pass it)
  246.  *
  247.  *   orig   96.4   2038   161   32000 random numbers (ascii sort)
  248.  *   this   174     271    54   same
  249.  *   pass   111
  250.  *
  251.  *   orig   17.3   100.7   49   words.doc (9628 words)
  252.  *   this   40        61   17
  253.  *   pass   23
  254.  *
  255.  */
  256. #include <stdio.h>
  257. #include <ctype.h>
  258. #include <string.h>
  259. #include <malloc.h>
  260. #define   FALSE   0
  261. #define   TRUE   1
  262. #define   EOS   0
  263. #include  <sys/types.h>
  264. #include  <sys/timeb.h>
  265. #undef    tolower
  266.  
  267. #define MX_RLINE 600          /* number of lines in a run */
  268. #define TEMP "sort.tmp"
  269. #define MAX_WK_FILES 1        /* # of different work-files to use */
  270. #define MAX_KEYS 11           /* Max number of key fields that can be specified */
  271. #define H_P_READ 8            /* # of lines a heapelt can hold */
  272.  
  273. typedef char BYTE;
  274.  
  275. /*********** */
  276. /* These change the way internal routines perform */
  277. #define TREEVER    /* verify the tree after doing the reheap */
  278. #undef  TREEVER
  279. #define REPLPUT    /* read replacement lines in putline */
  280. #undef  REPLPUT
  281.  
  282. struct work_file {
  283.    char w_filename[35];
  284.    FILE *w_fp;
  285. };
  286.  
  287. struct run {
  288.    struct run *r_rp;
  289.    long r_seek;
  290.    int r_size;
  291. };
  292.  
  293. struct heap_s {
  294.    char *h_lp_a[H_P_READ];
  295.    struct run *h_rp;
  296. };
  297.  
  298. struct run *crp  = NULL;   /* current run ptr */
  299. struct run *frp  = NULL;   /* 1st run ptr */
  300. struct run *lrp  = NULL;   /* last run ptr */
  301.  
  302. struct work_file wkf[MAX_WK_FILES];
  303.  
  304. char **line = NULL;
  305. int first_out = TRUE;   /* This is the 1st output line */
  306.  
  307. FILE *ofp = NULL;
  308. FILE *tfp = NULL;
  309. FILE *ifp = NULL;
  310. char *ofn = NULL;
  311. struct heap_s *heap;
  312. int nline = 0;
  313. int nruns = 0;
  314. int max_mline = 0;   /* max # of lines we can hold in memory during merge*/
  315. int pre_lines = 0;   /* # of lines actually pre-read into memory */
  316.  
  317. long int in_records = 0;   /* # of records read from the input files */
  318. long int in_bytes = 0;     /* # of bytes in them */
  319.  
  320. /*** This doubles as the input buffer and the detailed usage help
  321.  * info. It had better be at least 200 bytes long. */
  322. /*
  323. char   lbuf[] = "-b  ignore leading blanks\n-d  dictionary order\n\
  324. -f  fold letters to lowercase for compare\n\
  325. -i  ignore non-printing chars\n\
  326. -km1.n1,m2.n2 select key field (max 9 keys)\n-n  numeric comparison\n\
  327. -oOUT  specify output file (otherwise it is stdout)\n\
  328. -r  reverse order to descending\n\
  329. -t? specify field terminator char\n\
  330. -u  output only 1st line with equal keys\n\
  331. -v  verbose\n";
  332. */
  333. int nlbuf = -1;        /* length of string in lbuf (<0 means none) */
  334. char **llout = NULL;   /* last line put out (for -u) */
  335.  
  336. int dflag[MAX_KEYS];     /* dictionary order */
  337. int iflag[MAX_KEYS];     /* ignore all whitespace */
  338. int fflag[MAX_KEYS];     /* fold upper-case to lower-case */
  339. int vflag = 0;           /* give elapsed times, etc */
  340. int hard_way[MAX_KEYS];  /* if any of the above are set, this
  341.                           * comparison must be done the hard way.*/
  342. int uflag = 0;           /* only output 1st of set of lines with
  343.                           * equal keys */
  344. int nflag[MAX_KEYS];     /* numeric comparison (else alphabetic) */
  345. int rflag[MAX_KEYS];     /* reverse sort sense
  346.                           * (descending instead of ascending) */
  347. int bflag[MAX_KEYS];     /* ignore leading whitespace */
  348. char term_char[MAX_KEYS];/* field terminator character */
  349. int kflag = 0;           /* number of field specifiers (0 = none) */
  350.  
  351. /***** m1/n1 specify the 1st character of the key */
  352. int m1[MAX_KEYS];   /* fields to skip to start-of-key */
  353. int n1[MAX_KEYS];   /* chars to skip from start-of-field */
  354.  
  355. /***** m2/n2 specify the 1st character after the key. This char isn't
  356.  *   included in the key. */
  357. int m2[MAX_KEYS] = { -1 };   /* Number of fields to skip to end-of-key.
  358.                               * -1 means 'end of line' */
  359. int n2[MAX_KEYS];            /* chars to skip from end-of-key field */
  360.  
  361. extern char *getline();
  362. extern char *xalloc();
  363. extern int compare();       /* compare routine */
  364. extern qsort();             /* the sorting routine */
  365. struct heap_s heap_tmp;     /* temp area for the reheap */
  366.  
  367. extern long int systime();  /* time in msec since midnight */
  368. long int start_time;
  369.  
  370. main(argc, argv)
  371. char *argv[];
  372. {
  373.    register struct run *rp;
  374.    register char *cp;
  375.    char *cptmp;
  376.    char *argsave;
  377.    struct heap_s *hp;
  378.    int c, i, nf;
  379.  
  380.    start_time = systime();      /* init for elapsed time */
  381.    nf = argc - 1;
  382.    for (i=1; i<argc; ++i)
  383.    {
  384.       cp = argsave = argv[i];
  385.       if (*cp == '-')
  386.       {
  387.          --nf;
  388.          argv[i] = NULL;
  389.          ++cp;
  390.          while (c = *cp++)
  391.          {
  392.             switch (tolower(c))
  393.             {
  394.             case 'v':
  395.                vflag++;
  396.                break;
  397.  
  398.             case 'n':
  399.                ++nflag[kflag];
  400.                break;
  401.  
  402.             case 'b':
  403.                ++bflag[kflag];
  404.                break;
  405.  
  406.             case 'd':
  407.                ++dflag[kflag];
  408.                ++hard_way[kflag];
  409.                break;
  410.  
  411.             case 'i':
  412.                ++iflag[kflag];
  413.                ++hard_way[kflag];
  414.                break;
  415.  
  416.             case 'f':
  417.                ++fflag[kflag];
  418.                ++hard_way[kflag];
  419.                break;
  420.  
  421.             case 'u':
  422.                ++uflag;
  423.                break;
  424.  
  425.             case 'o':
  426.                if (*cp == NULL)     /* value is next arg */
  427.                {
  428.                   if (++i >= argc)
  429.                      usage("argument need after", argsave, c);
  430.                   /* no next arg, error! */
  431.                   if (*(ofn = argv[i]) == '-')
  432.                      usage("next argument may not be an option", argsave, c);
  433.                   /* next arg is itself an arg!! */
  434.                   argv[i] = NULL;   /* eliminate the arg   */
  435.                }
  436.                else       /* value is in this arg */
  437.                   ofn = cp;
  438.                cp = argv[i];   /* re-examine current arg (to skip it) */
  439.                --nf;
  440.                break;
  441.  
  442.             case 'r':
  443.                ++rflag[kflag];
  444.                break;
  445.  
  446.             case 'k':
  447.                defin_key(cp);
  448.                kflag++;
  449.                m1[kflag] = n1[kflag] = n2[kflag] = 0; 
  450.                m2[kflag] = -1;
  451.                bflag[kflag] = rflag[kflag] = nflag[kflag] = 0;
  452.                iflag[kflag] = fflag[kflag] = dflag[kflag] = 0;
  453.                hard_way[kflag] = term_char[kflag] = 0;
  454.                cp = &argv[i];
  455.                break;
  456.  
  457.             case 't':
  458.                if ((c = *cp++) == EOS)
  459.                   usage("no field separator after 't' option",
  460.                   argsave, c);
  461.                if (c == '\\')        /* escaped char */
  462.                {
  463.                   if (*cp == NULL)
  464.                      usage("no field separator after 't\\' option",
  465.                      argsave, c);
  466.                   cptmp = cp;
  467.                   c = esc_char(&cptmp);   
  468.                   cp = cptmp;
  469.                }
  470.                term_char[kflag] = c;
  471.                break;
  472.  
  473.             default:
  474.                usage("unknown option", argsave, c);
  475.             }
  476.          }
  477.       }
  478.    }
  479.    if (nf == 0)
  480.       ifp = stdin;
  481.    if ((tfp = fopen(TEMP, "w")) == NULL) {
  482.       fprintf(stderr, "Cannot create temp file.\n");
  483.       exit(1);
  484.    }
  485.    strcpy(wkf[0].w_filename, TEMP);
  486.    line = xalloc(MX_RLINE * sizeof(char *));
  487.    crp = xalloc(sizeof(struct run));
  488.    crp->r_size = 0;
  489.    /* There is always an implied last key of: ascii, ascending order,
  490.     *   using the entire line.
  491.     */
  492.    if (kflag == 0)
  493.       kflag++;
  494.    m1[kflag] = n1[kflag] = n2[kflag] = 0; 
  495.    m2[kflag] = -1;
  496.    bflag[kflag] = rflag[kflag] = nflag[kflag] = 0;
  497.    iflag[kflag] = fflag[kflag] = dflag[kflag] = 0;
  498.    hard_way[kflag] = term_char[kflag] = 0;
  499.    if (m1[kflag] == m1[kflag-1] && n1[kflag] == n1[kflag-1] &&
  500.        m2[kflag] == m2[kflag-1] && n2[kflag] == n2[kflag-1])
  501.       if (bflag[kflag] == bflag[kflag-1] && rflag[kflag] == rflag[kflag-1] &&
  502.           nflag[kflag] == nflag[kflag-1] && iflag[kflag] == iflag[kflag-1])
  503.          if (fflag[kflag] == fflag[kflag-1] && dflag[kflag] == dflag[kflag-1] &&
  504.              term_char[kflag] == term_char[kflag-1])
  505.             kflag--;
  506.    /*** Distribution phase. Create sorted runs from the input file(s)
  507.     * to the temp file(s). */
  508.    for (;;)
  509.    {
  510.       if (ifp == NULL)
  511.       {
  512.          for (i = 1; i < argc; ++i)   /* find next file-name argument */
  513.             if ((cp = argv[i]) != NULL)
  514.                break;
  515.          if (i >= argc)
  516.             break;
  517.          argv[i] = NULL;
  518.          if ((ifp = fopen(cp, "r")) == NULL)
  519.          {
  520.             fprintf(stderr, "%s: cannot open.\n", cp);
  521.             quit();
  522.          }
  523.       }
  524.       get_in_line();      /* get line from input */
  525.       if (nlbuf >= 0)
  526.       {
  527.          if (nline >= MX_RLINE || (cp = malloc(nlbuf + sizeof(char))) == NULL)
  528.          {
  529.             do
  530.             {
  531.                qsort(line, nline, sizeof(line[0]), compare);
  532.                saverun();
  533.                putline(tfp);
  534.                crp = xalloc(sizeof(struct run));
  535.                crp->r_size = 0;
  536.             } while (nline == MX_RLINE);
  537.             if (nlbuf >= 0)
  538.                cp = xalloc(nlbuf + sizeof (char));
  539.          }
  540.          if (nlbuf >= 0)
  541.          {
  542.             strcpy(cp, lbuf);
  543.             nlbuf = -1;
  544.             line[nline++] = cp;
  545.          }
  546.       }
  547.    }
  548.    qsort(line, nline, sizeof (line[0]), compare);
  549.    if (frp == NULL)   /* We have only 1 run, so put it right out. */
  550.    {
  551.       openoutput();
  552.       if (uflag)
  553.          llout = xalloc(sizeof(lbuf));
  554.       putline(ofp);
  555.       pr_eltim("Completed, all data fit in memory");
  556.       quit();
  557.    }
  558.  
  559.    /*** Merge phase. We are all done with the input files. */
  560.    if (nline > 0)
  561.    {
  562.       saverun();
  563.       putline(tfp);
  564.    }
  565.    fclose(tfp);
  566.  
  567.    pr_eltim("Distribution phase complete");
  568.    start_time = systime();
  569.    free(line);
  570.    if (uflag)
  571.       llout = xalloc(sizeof(lbuf));
  572.    openoutput();
  573.    if ((tfp = fopen(wkf[0].w_filename, "r")) == NULL)
  574.       panic("Cannot reopen temp file.\n");
  575.    heap = xalloc(nruns * sizeof(struct heap_s));
  576.  
  577.    /* See how many lines can be pre-read form the various runs. All this is
  578.     * in an attempt to read several lines from a run into memory each time
  579.     * we read, because the seek time is most of the time expense of the
  580.     * merge phase.
  581.     * We are limited by: 1) the size of the h_lps array in a heap element,
  582.     * and 2) the amount of memory we have available to put these lines into.
  583.     * To arrive at the memory we have/need, allocate as much as we need.
  584.     * This will most likely fail (no way is a very large file going to
  585.     * fit in memory). This failure point defines the max # of lines we will
  586.     * be able to hold. There is a safety margin here, but bad luck could
  587.     * cause the alloc to fail during the merge. If this happens, bump up
  588.     * the safety margin. With any luck, using the average record size will
  589.     * be good enough.
  590.    */
  591.    i = nruns * H_P_READ;
  592.    if (i > in_records)
  593.       i = in_records;
  594.    c = in_bytes / in_records;
  595.    if (c < (sizeof(int)))
  596.       c = sizeof(int);
  597.    lrp = xalloc(25 * c);   /* alloc a safety margin */
  598.    lrp->r_rp = NULL;
  599.    while (i-- && (crp = malloc(c)) != NULL)
  600.    {
  601.       crp->r_rp = lrp;
  602.       lrp = crp;
  603.       max_mline++;
  604.    }
  605.    /* now free the space all up */
  606.    while (lrp != NULL)
  607.    {
  608.       crp = lrp;
  609.       lrp = lrp->r_rp;
  610.       free(crp);
  611.    }
  612.  
  613.    /* Read the same number of lines initially for all runs. */
  614.    i = max_mline / nruns;
  615.    if (i <= 0)
  616.       i = 1;
  617.    if (i > H_P_READ)
  618.       i = H_P_READ;
  619.    rp = frp;
  620.    hp = &heap[0];
  621.    while (rp != NULL)   /* init for the merge */
  622.    {
  623.       hp->h_rp = rp;
  624.       run_read(hp, i);
  625.       if (hp->h_lp_a[0] == NULL)
  626.          panic("Empty run.\n");
  627.       rp = rp->r_rp;
  628.       hp++;
  629.    }
  630.    /* Sort it, to get the heap initially set up. */
  631.    qsort (heap, nruns, sizeof (struct heap_s), compare);
  632.  
  633.    while (nruns)
  634.    {
  635.       cp = heap[0].h_lp_a[0];
  636.       if (llout)
  637.          sp_fputs(cp, ofp);
  638.       else
  639.          fputss(cp, ofp);
  640.       free(cp);
  641.       copy(&heap_tmp, &heap[0], sizeof (struct heap_s));
  642.       pre_lines--;   /* shift up the other pre-read lines */
  643.       copy(&heap_tmp.h_lp_a[0], &heap_tmp.h_lp_a[1], sizeof(heap_tmp.h_lp_a[0]) * (H_P_READ-1));
  644.       heap_tmp.h_lp_a[H_P_READ - 1] = NULL;
  645.       if (heap_tmp.h_lp_a[0] == NULL)   /* we used them all up */
  646.          run_read(&heap_tmp, H_P_READ);
  647.       if (heap_tmp.h_lp_a[0] == NULL)   /* Done with this run. */
  648.       {
  649.          pr_eltim("Run complete");
  650.          --nruns;
  651.          reheap(heap, nruns, sizeof (struct heap_s), &heap[nruns]);
  652.       }
  653.       else
  654.          reheap(heap, nruns, sizeof (struct heap_s), &heap_tmp);
  655.    }
  656.    if (vflag)
  657.    {
  658.       i = (systime() - start_time) /100;   /* get&print elapsed time*/
  659.       fprintf (stderr,"Merge Elapsed: %d.%01d sec\n", i/10, i%10);
  660.    }
  661.    quit();
  662. }
  663.  
  664.  
  665. /*********************************************/
  666. pr_eltim(why)
  667. char   *why;
  668. {
  669.    int i;
  670.  
  671.    if (!vflag)
  672.       return;
  673.    i = (systime() - start_time) /100;   /* get&print elapsed time*/
  674.    fprintf(stderr, "%s, %ld records, %ld bytes, run number %d.\n", why, in_records, in_bytes, nruns);
  675.    fprintf (stderr,"Elapsed time: %d.%01d sec\n", i/10, i%10);
  676. }
  677.  
  678. /*********************************************/
  679. /* Get the next line from the input file to "lbuf".
  680.  * ifp == NULL means input file is closed.
  681.  * nlbuf == length of the line in lbuf (<0 means nothing in lbuf).
  682. */
  683. get_in_line()
  684. {
  685.    if (ifp == NULL)
  686.       return;
  687.    if (fgetss(lbuf, sizeof lbuf, ifp) == NULL)
  688.    {
  689.       if (ifp != stdin)
  690.          fclose(ifp);
  691.       ifp = NULL;
  692.       nlbuf = -1;
  693.    }
  694.    else
  695.    {
  696.       nlbuf = strlen(lbuf);
  697.       in_records++; 
  698.       in_bytes += nlbuf;
  699.    }
  700. }
  701.  
  702. /*
  703.  * Open the output file and stash its file
  704.  * pointer in 'ofp'. If no output file is
  705.  * given 'ofp' is a dup. of 'stdout'.
  706.  */
  707. openoutput()
  708. {
  709.    if (ofn == NULL)
  710.       ofp = stdout;
  711.    else if ((ofp = fopen(ofn, "w")) == NULL)
  712.    {
  713.       fprintf(stderr, "%s: cannot create.\n", ofn);
  714.       quit();
  715.    }
  716. }
  717.  
  718. /******************************************/
  719. /* Special fputs, used for '-u' flag, to put out only
  720.  * unique lines.
  721.  * The very first line is deemed 'unique', and is always put out.
  722. */
  723. sp_fputs(buf, usr_file)
  724. char *buf;
  725. FILE *usr_file;
  726. {
  727.    if (com_par(&llout, &buf, kflag? kflag-1 : kflag) || first_out)
  728.    {
  729.       fputss(buf, usr_file); /* this line different from last */
  730.       first_out = FALSE;
  731.       strcpy (llout, buf);
  732.    }
  733. }
  734.  
  735. /**************************************/
  736. /* read some lines from a run into memory */
  737. run_read(helt, m_lines)
  738. struct heap_s *helt;   /* the heap element for this run */
  739. int m_lines;      /* max # of lines to read */
  740. {
  741.    int i;
  742.  
  743.    for (i = 0; i < m_lines && pre_lines <= max_mline; i++)
  744.    {
  745.       if ((helt->h_lp_a[i] = getline(helt->h_rp)) == NULL)
  746.          break;
  747.       pre_lines++;
  748.    }
  749.    if (i < H_P_READ)
  750.       helt->h_lp_a[i] = NULL;
  751. }
  752.  
  753.  
  754. /************************************************/
  755. /* convert escaped char to a char value. Update cp. */
  756. esc_char (cpp)
  757. char **cpp;
  758. {
  759.    register char c;   /* the converted character */
  760.    register char c1;
  761.    register char *p;   /* buffer ptr */
  762.  
  763.    p = *cpp;   /* point to the string */
  764.    c = tolower(*p++);
  765.    if (c == 't')
  766.       c = '\t';         /* \t is tab */
  767.    else if (c == 's')
  768.       c = ' ';         /* \s is space */
  769.    else if (c >= '0' && c <= '7')   /*  \digits is the obvious */
  770.    {
  771.       c -= '0';
  772.       while ((c1 = *p++) >= '0' && c1 <= '7')
  773.          c = (c<<3) + (c1 - '0');
  774.       p--;         /* back up, we went too far */
  775.    }
  776.    else            /* anything else is itself */
  777.      c = *(p-1);
  778.    *cpp = p;       /* update the buffer pointer */
  779.    return (c);
  780. }
  781. /******************** routines passed into quicksort *******/
  782. /*
  783.  * Compare routine.
  784.  */
  785. static int compare(sa, sb)
  786. char *sa[], *sb[];
  787. {
  788.    return (com_par(sa, sb, kflag));
  789. }
  790.  
  791.  
  792.  
  793. static int com_par(sa, sb, num_keys)
  794. char *sa[], *sb[];
  795. int num_keys;   /* max number of keys to examine */
  796. {
  797.    extern char *get_to_key();
  798.    register char *a, *b;
  799.    register c;
  800.    char ch;
  801.    long d, atol();
  802.    int field_num;         /* field number loop counter */
  803.    char *aeok_ptr, *beok_ptr;   /* for saving the char after the key */
  804.    char aeok_char, beok_char;
  805.  
  806.    c = 0;
  807.    for (field_num = 0; !c && (field_num <= num_keys); field_num++)
  808.    {
  809.       /* find the key-field addresses */
  810.       aeok_ptr = beok_ptr = &ch;   /* in case EOK = EOL */
  811.       a = get_to_key(m1[field_num], n1[field_num], m2[field_num], n2[field_num],
  812.         bflag[field_num], *sa, &aeok_ptr, term_char[field_num]);
  813.       b = get_to_key(m1[field_num], n1[field_num], m2[field_num], n2[field_num],
  814.         bflag[field_num], *sb, &beok_ptr, term_char[field_num]);
  815.       aeok_char = *aeok_ptr; 
  816.       *aeok_ptr = NULL;   /* terminate keys */
  817.       beok_char = *beok_ptr; 
  818.       *beok_ptr = NULL;   /* terminate keys */
  819.       /*fprintf(stderr,"a key:'%s'\n", a);*/
  820.  
  821.       if (nflag[field_num])
  822.       {
  823.          if ((d = atol(a)-atol(b)) < 0)
  824.             --c;
  825.          else if (d > 0)
  826.             ++c;
  827.       }
  828.       else if (hard_way[field_num])
  829.          c = hard_cmp(a, b, iflag[field_num], dflag[field_num], fflag[field_num]);
  830.       else
  831.          c = strcmp(a, b);
  832.       /* restore the char after the keys */
  833.       *aeok_ptr = aeok_char;
  834.       *beok_ptr = beok_char;
  835.       if (rflag[field_num])
  836.          c = -c;
  837.    }
  838.    return (c);
  839. }
  840.  
  841. /***************/
  842. /* return pointer to the next field of the string.
  843.  * A field is defined as: optional whitespace followed by
  844.  *   non-whitespace; the next field is the next
  845.  *   whitespace or NULL.
  846.  *
  847.  * The returned result is a pointer to this 1st char of the
  848.  * next field.
  849.  * It will never advance past the trailing NULL.
  850. */
  851. char *nxt_fld(s, tch)
  852. register char *s;
  853. register char tch;   /* field terminator char or NULL */
  854. {
  855.    register char c;
  856.  
  857.    if (tch != NULL) 
  858.       while (*s != NULL && *s++ != tch)
  859.          ;
  860.    else
  861.    {
  862.       while (((c = *s) != EOS) && isspace(c) != 0)
  863.          s++;
  864.       while (((c = *s) != EOS) && isspace(c) == 0)
  865.          s++;
  866.    }
  867.    return (s);
  868. }
  869.  
  870. /*****************************************/
  871. /********* get the definition for a key field  */
  872. defin_key(cp)
  873. char *cp;
  874. {
  875.    if (kflag >= MAX_KEYS - 1)
  876.       panic ("Too many keys specified\n");
  877.  
  878.    n1[kflag] = n2[kflag] = 0; 
  879.    m2[kflag] = -1;
  880.    m1[kflag] = atodl(&cp);
  881.    if (*cp == '.')
  882.    {
  883.       cp++;      /* char adv from start of field */
  884.       n1[kflag] = atodl(&cp);
  885.    }
  886.    if (!*cp++)
  887.       return;   /* no end-of-key */
  888.  
  889.    m2[kflag] = atodl(&cp);
  890.    if (!*cp)
  891.       return;
  892.    if (*cp++ != '.')
  893.       panic ("Invalid key field format\n");
  894.    n2[kflag] = atodl(&cp);
  895.  
  896.    return;
  897. }
  898.  
  899. /*****************/
  900. /* unsigned ascii to decimal conversion.
  901.  * stops on a non-digit. Update the buffer pointer to
  902.  * point to this terminating non-digit.
  903. */
  904. int atodl(cp)
  905. char **cp;
  906. {
  907.    register int n;
  908.    register char *p;
  909.    register char ch;
  910.  
  911.    n = 0;
  912.    p = *cp;   /* point to the string */
  913.    while (isdigit((ch = *p++)))
  914.       n = 10*n + (ch - '0');
  915.    *cp = p-1;   /* update the buffer pointer */
  916.    return (n);
  917. }
  918.  
  919. /************************************************/
  920. /* get pointers to the start-of-key, and end-of-key.
  921.  * returns ptr to 1st char of the key.
  922.  * "eok_ptr" points to next char after the key, unless eok = "end-of-line".
  923.  * The pointers will never go past the NULL.
  924.  * eok-ptr will never be before sok-ptr.
  925. */
  926. char *get_to_key (sok_fld, sok_adv, eok_fld, eok_adv, skip_ws, str, eok_ptr, term_ch)
  927. int sok_fld, sok_adv;   /* start-of-key fields & chars to skip*/
  928. int eok_fld, eok_adv;   /* end-of-key fields & chars to skip*/
  929. int skip_ws;            /* skip leading whitespace before advancing by chars*/
  930. char *str;              /* the string */
  931. char **eok_ptr;         /* set to point to the 1st char after the key,
  932.                          * if any eok was specified. 
  933.                          * otherwise not modified. */
  934. char term_ch;           /* field terminator or NULL */
  935. {
  936.    register char *kptr;   /* start-of-key pointer */
  937.    register char *eptr;   /* end-of-key pointer */
  938.    register int i;
  939.    char ch;
  940.  
  941.    /* skip over fields to get to start-of-key */
  942.    kptr = str;   /* init to start of line */
  943.    i = sok_fld;
  944.    while (i--)
  945.       kptr = nxt_fld(kptr, term_ch);
  946.    /* probably we can keep going forward from the SOK to EOK field */
  947.    i = eok_fld - sok_fld;   
  948.    eptr = kptr;
  949.    /* advance SOK ptr by chars (never past end) */
  950.    if (skip_ws)
  951.       while ((ch = *kptr) && isspace(ch) != 0)
  952.          kptr++;
  953.    while (sok_adv-- && *kptr++)
  954.       ;
  955.    if (eok_fld >= 0)   /* position to eok field*/
  956.    {
  957.       if (i < 0)
  958.       {
  959.          i = eok_fld;   /* eok search from start of line */
  960.          eptr = str;
  961.       }
  962.       while (i--)
  963.          eptr = nxt_fld(eptr, term_ch);
  964.       /* advance eok ptr by chars (never past end) */
  965.       if (skip_ws)
  966.          while ((ch = *eptr) && isspace(ch) != 0)
  967.             eptr++;
  968.       while (eok_adv-- && *eptr++)
  969.          ;
  970.       *eok_ptr = eptr;      /* return ptr to char after key */
  971.       if (eptr < kptr)
  972.          *eok_ptr = kptr;   /* force null key */
  973.    }
  974.    return (kptr);
  975. }
  976.  
  977. /*************************************************************/
  978. /* string comparisons the hard-way, one character at a time, 
  979.  * because one of the special flags was set.
  980. */
  981. hard_cmp(a, b, ifl, dfl, ffl)
  982. register char *a, *b;   /* the two strings to compare */
  983. int ifl;                /* ignore all whitespace */
  984. int dfl;                /* dictionary order, ignore all but letters, digits,
  985.                          * and blanks
  986.                          */
  987. int ffl;                /* fold upper-case to lower case before compare */
  988. {
  989.    register char achar, bchar;
  990.    int c;               /* result */
  991.  
  992.    c = 0;
  993.    while (!c && (achar = *a) && (bchar = *b))
  994.    {
  995.       if (dfl)     /* dictionary-style */
  996.       {
  997.          while ((achar = *a) && !(isdigit(achar) || isalpha(achar) || (achar == ' ')))
  998.             a++;
  999.          while ((bchar = *b) && !(isdigit(bchar) || isalpha(bchar) || (bchar == ' ')))
  1000.             b++;
  1001.       }
  1002.       if (ifl)
  1003.       {             /* ignore all whitespace */
  1004.          while ((achar = *a) && isspace(achar))
  1005.             a++;
  1006.          while ((bchar = *b) && isspace(bchar))
  1007.             b++;
  1008.       }
  1009.       if (ffl)
  1010.       {   /* fold to lower-case */
  1011.          achar = tolower(achar);
  1012.          bchar = tolower(bchar);
  1013.       }
  1014.       c = achar - bchar;
  1015.       if (!c && achar)
  1016.          a++;
  1017.       if (!c && bchar)
  1018.          b++;
  1019.    }
  1020.    if (!c)
  1021.       c = achar - bchar;
  1022.    return(c);
  1023. }
  1024. /*
  1025.  * Rebuild a heap.
  1026.  * This is essentially TREESORT.
  1027.  * Used to reorder the heap when a new item is read into it.
  1028.  * The 'heap' is a binary tree, such that for each node 'i', the key at
  1029.  * 'i' is the lowest of it and it's two sons, (2*i + 1) and (2*i + 2).
  1030.  * The new element is to be inserted where it should go.
  1031.  * We can move things up in the heap, as array element [0] is empty.
  1032.  * At each step, h[i] is empty.
  1033.  */
  1034.  
  1035. reheap(h, n, elt_size, new_elt)
  1036. BYTE h[];                 /* The array which is the heap */
  1037. int n;                    /* number of elements in array h*/
  1038. int elt_size;             /* size of array element in bytes */
  1039. struct heap_s *new_elt;   /* new element to be added */
  1040. {
  1041.    register int i, j;
  1042.    BYTE *ip, *jp, *jp1;   /* ptrs for i, j, j+1 */
  1043.  
  1044.    for (i = 0, ip = h; (j = 2*i+1) < n; i = j, ip = jp)
  1045.    {
  1046.       jp = h+(j*elt_size);
  1047.       jp1 = jp + elt_size;
  1048.       if ((j+1 < n) && (compare(jp1, jp) < 0))
  1049.       {
  1050.          jp = jp1;
  1051.          ++j;
  1052.       }
  1053.       /* j now points to the smaller child of i */
  1054.       if (compare(new_elt, jp) <= 0)
  1055.          break;
  1056.       copy(ip, jp, elt_size);
  1057.    }
  1058.    copy(ip, new_elt, elt_size);
  1059. #ifdef   TREEVER   /**** verify that the tree is ok */
  1060.    for (i = 0; (j = 2*i+1) < nruns; i++)
  1061.    {
  1062.       if (h != heap)
  1063.          break;
  1064.       if ((j < nruns && compare(&heap[i].h_lp, &heap[j].h_lp) > 0) ||
  1065.           (j+1 < nruns && compare(&heap[i].h_lp,&heap[j+1].h_lp) > 0))
  1066.       {
  1067.          fprintf (stderr, "Tree out of order. n = %d. Index = %d.\n", nruns, i);
  1068.          fprintf (stderr,"addresses: %o %o %o\n", &heap[i], &heap[j], &heap[j+1]);
  1069.          fprintf (stderr,"nruns: %d\n%d->%s%d->%s%d->%s", nruns, i, heap[i].h_lp, j, heap[j].h_lp, j+1,
  1070.            j+1<nruns ? heap[j+1].h_lp : NULL);
  1071.          fprintf (stderr,"New->%s", new_elt->h_lp);
  1072.          fprintf (stderr,"At %o\n", new_elt);
  1073.          fprintf (stderr,"%d->%s", 0, heap[0].h_lp);
  1074.          for (i = 0; i <n; i++)
  1075.             fprintf (stdout, "%d->%s", i, heap[i].h_lp);
  1076.          abort();
  1077.       }
  1078.    }
  1079.    for (i = 0; (j = 2*i+1) < nline; i++)
  1080.    {
  1081.       if (h != line)
  1082.          break;
  1083.       if ((j < nline && compare(&line[i], &line[j]) > 0) ||
  1084.           (j+1 < nline && compare(&line[i],&line[j+1]) > 0))
  1085.       {
  1086.          fprintf (stderr, "Tree out of order. n = %d. Index = %d.\n", nline, i);
  1087.          fprintf (stderr,"addresses: %o %o %o\n", &line[i], &line[j], &line[j+1]);
  1088.          fprintf (stderr,"nline: %d\n%d->%s%d->%s%d->%s", nline, i, line[i], j, line[j], j+1,
  1089.            j+1<nline ? line[j+1] : NULL);
  1090.          for (i = 0; i <n; i++)
  1091.             fprintf (stdout, "%d->%s", i, line[i]);
  1092.          abort();
  1093.       }
  1094.    }
  1095. #endif
  1096. }
  1097.  
  1098. /*
  1099.  * Save a run.
  1100.  * The run block has been preallocated
  1101.  * because there may not be enough space
  1102.  * to allocate it now.
  1103.  */
  1104. saverun()
  1105. {
  1106.    long ftell();
  1107.  
  1108.    crp->r_rp = NULL;
  1109.    crp->r_seek = ftell(tfp);
  1110.    if (frp == NULL)
  1111.       frp = crp;
  1112.    else
  1113.       lrp->r_rp = crp;
  1114.    lrp = crp;
  1115.    ++nruns;
  1116. }
  1117.  
  1118. /*
  1119.  * Get a line from the specified run
  1120.  * on the temp. file.
  1121.  * Pack the line into allocated storage
  1122.  * and return a pointer to it.
  1123.  * Return NULL if there are no lines left
  1124.  * in the run; real end of file is an
  1125.  * internal botch.
  1126.  */
  1127. char *getline(rp)
  1128. register struct run *rp;
  1129. {
  1130.    register char *cp;
  1131.    long ftell();
  1132.  
  1133.    if (rp->r_size == 0)
  1134.       return (NULL);
  1135.    fseek(tfp, rp->r_seek, 0);
  1136.    if (fgetss(lbuf, sizeof lbuf, tfp) == NULL)
  1137.       panic("Unexpected end of file\n");
  1138.    rp->r_seek = ftell(tfp);
  1139.    --rp->r_size;
  1140.    cp = xalloc(strlen(lbuf) + sizeof(char));
  1141.    strcpy(cp, lbuf);
  1142.    return (cp);
  1143. }
  1144.  
  1145. /*************************/
  1146. /* Dump the lines in the array to the file.   */
  1147. putline(fp)
  1148. FILE *fp;   /* the output fp */
  1149. {
  1150.    register int ilater;   /* ptr for lines that can't go in this run */
  1151.    register int i;
  1152.    register char *cp;
  1153. #ifdef REPLPUT
  1154.    char *ncp;
  1155. #endif
  1156.  
  1157.    crp->r_size = nline;
  1158. #ifndef REPLPUT
  1159.    for (i = 0; i < nline; i++)
  1160.    {
  1161.       cp = line[i];
  1162.       if (llout)
  1163.          sp_fputs(cp, fp);
  1164.       else
  1165.          fputss(cp, fp);
  1166.       free(cp);
  1167.    }
  1168.    nline = 0;
  1169. #else
  1170.  
  1171.    /*
  1172.     * To improve the length of the runs, replace each line as it goes out.
  1173.     * If it can, it will become part of this run, otherwise it will be
  1174.     * saved up to be part of the next run.
  1175.     *
  1176.     * In general, when this routine returns, the array will be filled with
  1177.     * lines that wouldn't go in this run. This will be the case except when
  1178.     * we hit EOF on the input.
  1179.     *
  1180.     * The next input line is already in lbuf.
  1181.     */
  1182.    ilater = MX_RLINE;
  1183.    while (nline > 0)
  1184.    {
  1185.       cp = line[0];
  1186.       if (llout)
  1187.          sp_fputs(cp, fp);
  1188.       else
  1189.          fputss(cp, fp);
  1190.       if (nlbuf >= 0 && crp->r_size < 30000 && (ncp = malloc(nlbuf + sizeof(char))) != NULL) {
  1191.          strcpy(ncp, lbuf);
  1192.          get_in_line();
  1193.          if (compare(&ncp, &cp) >= 0)
  1194.          {  /* the line can be in this run */
  1195.             crp->r_size++;
  1196.             reheap(line, nline, sizeof(line[0]), &ncp);
  1197.          }
  1198.          else
  1199.          {   /* it will be part of the next run */
  1200.             nline--;
  1201.             reheap (line, nline, sizeof(line[0]), &line[nline]);
  1202.             line[--ilater] = ncp;   /* tuck it away */
  1203.          }
  1204.       }
  1205.       else
  1206.       {  /* nothing to replace with */
  1207.          nline--;
  1208.          reheap(line, nline, sizeof(line[0]), &line[nline]);
  1209.       }
  1210.       free(cp);
  1211.    }
  1212.  
  1213.    /* The new replacement lines that couldn't become part of
  1214.     * this run are at the end of the array. Move them up and adjust the
  1215.     * index.
  1216.    */
  1217.    nline = MX_RLINE - ilater;
  1218.    if (nline != 0 && ilater != 0)
  1219.       copy(&line[0], &line[ilater], nline * sizeof(line[0]));
  1220. #endif
  1221. }
  1222.  
  1223. /*
  1224.  * Allocate space.
  1225.  * If no space, abort with a nasty
  1226.  * little message.
  1227.  */
  1228. char *xalloc(n)
  1229. {
  1230.    register char *p;
  1231.  
  1232.    if ((p = malloc(n)) == NULL)
  1233.    {
  1234.       fprintf(stderr, "Out of space.\n");
  1235.       exit(1);
  1236.    }
  1237.    return (p);
  1238. }
  1239.  
  1240. /*
  1241.  * Quit.
  1242.  * Get rid of the temp. file.
  1243.  * Exit.
  1244.  */
  1245. quit()
  1246. {
  1247.    if (tfp != NULL)
  1248.       unlink(tfp);
  1249.    exit(0);
  1250. }
  1251.  
  1252. /*
  1253.  * Tell the user just what is expected
  1254.  * of him.
  1255.  */
  1256. usage(why, argsave, c)
  1257. char *why;
  1258. char *argsave;
  1259. char  c;
  1260. {
  1261.    if (c != '?')
  1262.    {
  1263.       fprintf(stderr, "Sort error: %s", why);
  1264.       if (c == EOS)
  1265.          fprintf(stderr, "\nat end of option string");
  1266.       else if (c < ' ')
  1267.          fprintf(stderr, " at CTRL/%c", c + '@');
  1268.       else
  1269.          fprintf(stderr, " at '%c'", c);
  1270.       fprintf(stderr, ", argument = \"%s\"\n", argsave);
  1271.    }
  1272.    fprintf(stderr, "Usage: sort [-bdfinrt?uv] [-[bdfinrt?]km1.n1,m2.n2]");
  1273.    fprintf (stderr, " [-k...]\n\t    [-oOUTFILE] [file ...]\n");
  1274.    if (c == '?')
  1275.       printf(lbuf);
  1276.    exit(1);
  1277. }
  1278.  
  1279. /*
  1280.  * Errors.
  1281.  * Print a message and die with "error" status on RT/RSX,
  1282.  * "error" on UNIX (I think).
  1283.  */
  1284. errxit(a)
  1285. {
  1286.    fprintf(stderr,"?SORT-F-%r", &a);
  1287.    exit(0);
  1288. }
  1289.  
  1290. /*
  1291.  * Fatal errors.
  1292.  * Print a message and die.
  1293.  */
  1294. panic(a)
  1295. {
  1296.    fprintf(stderr, "Panic: %r", &a);
  1297.    exit(0);
  1298. }
  1299.  
  1300. static int time_first = TRUE;
  1301. static struct timeb   first_time;
  1302.  
  1303. long int systime()
  1304. /*
  1305.  * Returns elapsed time in milliseconds
  1306.  */
  1307. {
  1308.    long time, millisec;
  1309.    struct timeb time_buffer;
  1310.  
  1311.    if (time_first)
  1312.    {
  1313.       /*
  1314.        * This makes sure we can store enough milliseconds in 32 bits
  1315.        */
  1316.       ftime(&first_time);
  1317.       time_first = FALSE;
  1318.    }
  1319.    ftime(&time_buffer);
  1320.    time = time_buffer.time - first_time.time;
  1321.    millisec = time_buffer.millitm - first_time.millitm;
  1322.    time *= 1000;
  1323.    return (time + millisec);
  1324. }
  1325.